//
//  Problem856.swift
//  TestProject
//
//  Created by 武侠 on 2021/3/26.
//  Copyright © 2021 zhulong. All rights reserved.
//

import UIKit

/*
 856. 括号的分数
 给定一个平衡括号字符串 S，按下述规则计算该字符串的分数：
 () 得 1 分。
 AB 得 A + B 分，其中 A 和 B 是平衡括号字符串。
 (A) 得 2 * A 分，其中 A 是平衡括号字符串。
  
 示例 1：
     输入： "()"
     输出： 1
 示例 2：
     输入： "(())"
     输出： 2   => 2 * 1
 示例 3：
     输入： "()()"
     输出： 2      => 1 + 1
 示例 4：
     输入： "(()(()))"
     输出： 6      => (1 + 1 * 2) * 2
 提示：
     S 是平衡括号字符串，且只含有 ( 和 ) 。
     2 <= S.length <= 50
 */
@objcMembers class Problem856: NSObject {
    func solution() {
        print(scoreOfParenthesesDeep("()"))
        print(scoreOfParenthesesDeep("(())"))
        print(scoreOfParenthesesDeep("()()"))
        print(scoreOfParenthesesDeep("(()(()))"))
//        print(scoreOfParenthesesDeep("()()((()()))"))
//        print(scoreOfParenthesesDui("()()((()()))((()()))"))
    }
    
    
    /*
     
     1: 创建一个add = 0 和 mul = 1
     2: 遍历字符串, s[i] 有2种情况 "(" 或者 ")"
     3: 当s[i] == "(", 然后判断s[i-1]，如果s[i-1] == "(" => mul * 2;  s[i-1] == ")" => add = add + mul
     */
    func scoreOfParentheses(_ S: String) -> Int {
        var result = 0
        var add = 0
        var mul = 1
        
        var lastC: Character? = nil
        var leftNum = 0
        for c in S {
            if c == ")" {
                leftNum -= 1
                if lastC == "(" {
                    add += 1
                } else if lastC == ")" {
                    mul *= 2
                }
            } else {
                leftNum += 1
            }
            
            if leftNum == 0 {
                result += add *  mul
                print(add, mul, result)
                add = 0
                mul = 1
            }
            
            lastC = c
        }
        return result
    }
    
    /*
     1: 创建一个数组dui[Int]
     2: 遍历字符串, 对字符按照规则进行处理：
        2.1 如果是"(", 放入数组中 => ["("],
        2.2 如果是")", 数组中存储的最后一个是"("，那么把["("] => [1], 如果是数字，往前遍历，求和，直到找到-1，然后*2放入数组中
     例子：()(()())
     i = 0  => s[i] = '('  => 放入数组中 => ['(']
     i = 1  => s[i] = ')'  => 数字最后一位是'(', 那么数组变成 [1]
     i = 2  => s[i] = '('  => 放入数组中 => [1, '(']
     i = 3  => s[i] = '('  => 放入数组中 => [1, '(', '(']
     i = 4  => s[i] = ')'  => 数字最后一位是'(', 那么数组变成 => [1, '(', 1]
     i = 5  => s[i] = '('  => 放入数组中 => [1, '(', 1, '(']
     i = 6  => s[i] = ')'  => 数字最后一位是'(', 那么数组变成 => [1, '(', 1, 1]
     i = 7  => s[i] = ')'  => 数字最后一位是数字, 那么先求和知道遇到'(', 然后和*2 那么数组变成 => [1, 4]
     3: 求数组的和
     */
    func scoreOfParenthesesDui(_ S: String) -> Int {
        var dui:[Int] = []
        for c in S {
            if c == "(" {
                dui.append(-1)
            } else {
                
                var temp = 0
                while dui.count > 0 {
                    let last = dui.removeLast()
                    if last == -1 {
                        temp *= 2
                        break
                    } else {
                        temp += last
                    }
                }
                dui.append(temp == 0 ? 1 : temp)
            }
        }
        return dui.reduce(0) { (fir, sec) -> Int in
            return fir + sec
        }
    }
    
    /*
     思路：正在确定值的只有()，所以遇到"()"时，就结束 计算一次
     1: 创建一个遍历v，计算深度，
     2: 遍历字符串，遇到一个 ( ：深度+1
     3: 遇到一个)，并且上一个字符是(，意味着遇到() 计算一次：result += v
     注意：((()())) 中间有2个() 他俩的深度一直
     */
    func scoreOfParenthesesDeep(_ S: String) -> Int {
        var v = 0       // 计算深度
        var LastC: Character? = nil
        var result = 0
        for c in S {
            if c == "(" {
                v += 1      // 深度+1
            } else {
                v -= 1      // 深度-1
                if LastC == "(" {       // 遇到了一个()
                    // 深度计算 * 2
//                    var t = 1
//                    if v > 0 {
//                        for _ in 0..<v {
//                            t *= 2
//                        }
//                    }
                    
//                    result += t
                    result += 1 << v
                }
            }
            LastC = c
        }
        return result
    }
}
